package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-05-19 17:49
 */
public class 题库_0022_括号生成 {

  static
  class Solution {
    public List<String> generateParenthesis(int n) {
      List<String> answer = new ArrayList<>();
      if (n <= 0) {
        return answer;
      }
      backtrack(answer, 0, 0, n, 0, new char[n * 2]);
      return answer;
    }

    private void backtrack(List<String> answer, int left, int right, int n, int index, char[] brackets) {
      if (index == brackets.length) {
        answer.add(new String(brackets));
        return;
      }

      // 放右括号
      if (left < n) {
        brackets[index] = '(';
        backtrack(answer, left + 1, right, n, index + 1, brackets);
      }

      // 放左括号，left must less than n
      if (right < left) {
        brackets[index] = ')';
        backtrack(answer, left, right + 1, n, index + 1, brackets);
      }
    }

  }

}
